The present invention relates cache memory management and more particularly to a simple technique for deciding whether or not to remove an object from cache storage.
Cache memories are relatively small buffer memories used in computer systems to provide temporary storage for data retrieved from larger, slower main memory devices, such as hard disk drives. Cache memories, if properly managed, can significantly improve computer system performance.
Cache memories are employed in many computer workstations. A central processing unit in a workstation needs less time to obtain data from a cache memory than it does to obtain the same data by accessing the main memory. If a reasonable percentage of the data needed by a central processing unit is maintained in cache memory, the amount of processor time wasted waiting for data to be retrieved from main memory is significantly reduced, improving the computer system performance.
Cache memories are also employed in network environments, exemplified by the Internet or World Wide Web. In a Web environment, a user (interacting through a personal computer) communicates with a Web host through a proxy server. One of the functions that a proxy server performs is caching of copies of data previously requested by the user. When the user submits a request for data, a proxy server intercepts that request and determines whether it has already cached a copy of the requested data. If a cached copy exists, that copy is returned to the user by the proxy server without ever forwarding request to the Web host. If a cached copy does not exist in the proxy server, the server then forwards the user""s request to the Web host. When the Web host returns the requested data, the proxy server attempts to cache a copy of the data before passing it on to the user.
If the requested data unit or object is found in the cache, this is called a xe2x80x9chitxe2x80x9d. If the object cannot be found in the cache, this is called a xe2x80x9cmissxe2x80x9d necessitating a xe2x80x9cfetchxe2x80x9d operation to retrieve the memory from the Web host.
In steady-state system operation, the cache becomes heavily loaded. A cache miss requires a fetch operation and also implies that some of the data already in the cache must be removed to make room for the data being fetched from main memory. Cache replacement techniques have been studied extensively. Use-based replacement techniques take into account the record of use for every cached object when making replacement decisions. Examples of this type of replacement technique are the xe2x80x9cLeast Recently Usedxe2x80x9d (LRU) approach or the xe2x80x9cworking setxe2x80x9d approach. Other approaches make removal/replacement decisions on the basis of factors unrelated to usage. A xe2x80x9cfirst-in-first-outxe2x80x9d or FIFO approach and a xe2x80x9crandom removalxe2x80x9d approach are examples of cache replacement techniques which do not take into account object usage.
Cache replacement techniques can place heavy demands on system resources. One known class of techniques requires that a number of cached objects be xe2x80x9crankedxe2x80x9d relative to one another to determine which object would be the xe2x80x9cbestxe2x80x9d one to remove. To make sure that cache replacement decisions can be made quickly enough, systems practicing xe2x80x9crankingxe2x80x9d techniques are typically implemented at least in part in hardware. Hardware implementations are costlier and less flexible than software implementations.
A similar situation is found for cache systems used in proxy servers. Once its cache is full, the proxy server must remove cached objects, also called documents, in order to free up space for newly received documents. In a network environment, cache replacement operations are sometimes referred to as garbage collection.
A proxy server is typically capable of storing large numbers of documents. Because of this, it is not always practical to use xe2x80x9crankingxe2x80x9d techniques in making cache replacement decisions. For this reason, garbage collection is sometimes performed at a certain time of day or is triggered only when the cache size exceeds a given limit.
Where large numbers of documents are stored, a proxy server may select a subset of the documents and assign a weight to each document in the subset. The weight may be based on an estimation of the probability that the particular document will be needed in the future. Once all the documents in the subset are assigned a weight, the documents are ranked relative to one another. A predetermined percentage of the documents is removed from the subset. One problem with this approach is trying to choose the size of the subset. If the subset is too small, it may not be statistically representative of the entire set. Removing a predetermined percentage of the documents in the subset may result in the removal of documents that ranked low in the subset but would have ranked relatively higher if the complete set of documents had been ranked. Making the subset larger is not complete solution since larger subsets increase computational demands on the system.
The present invention is a cache replacement technique that minimizes demands on system resources. When a cache replacement decision is to be made, an object is selected from the cache and assigned a weight in accordance with a predetermined methodology. The assigned object weight is compared to an existing threshold. If the assigned object weight is lower than the threshold, the object is marked for removal and the threshold value is reduced. If the assigned object weight is higher than the threshold, the object remains in the cache and the threshold level is raised. A reduction in the threshold level decreases the chances that the next object considered will be selected for replacement. An increase in the threshold level increases the chances that the next object considered will be selected for replacement.